// ========================================================
// * Integer Knapsack Problem (Duplicate Items Permitted) *
// ========================================================
// You have n types of items, where the i-th item type has an integer size Si and a real value Vi. You are
// trying to fill a knapsack of total capacity C with a selection of items of maximum value. You can add
// multiple items of the same type to the knapsack (duplicate items permitted).
//
//
// Algorithm: Dynamic Programming
// Let M(i) denote the maximum value that a knapsack of total capacity i can hold.
//
// Then, M(i)=max{M(i-1), max{M(i-s[j])+v[j]}|0<=j<n}, 0<i<=C
//       M(0)=0
// Therefore, M(C) is the optimal solution to the problem.
//
//
// Complexity
//  Time: O(n*C)
//  Space: O(C)

#include "stdafx.h"
#include <iostream>
using namespace std;

// *s: size array
// *v: value array
// n: number of item types
// c: knapsack capacity
int Knapsack(int *s, int *v, int n, int c)
{
    if(!s||!v||n<=0||c<0) throw;
    if(!c) return 0;

    int *M=new int[c+1];
    M[0]=0;

    for(int i=1;i<c+1;i++)
    {
        int max=0;
        for(int j=0;j<n;j++)
        {
            int value=(i>=s[j]) ? M[i-s[j]]+v[j]:0; // assume s[j]>0 and v[j]>0
            max=(max>value) ? max:value;
        }
        M[i]=(max>M[i-1]) ? max:M[i-1];
    }

    int maxValue=M[c];
    delete[] M;
    return maxValue;
}

int Knapsack_Recursion(int *s, int *v, int n, int c)
{
    if(!s||!v||n<=0||c<0) throw;
    if(!c) return 0;

    int max=0;
    for(int j=0;j<n;j++)
    {
        if(c<s[j]) continue;

        int value=Knapsack_Recursion(s,v,n,c-s[j])+v[j];
        max=(max>value) ? max:value;
    }

    int k=Knapsack_Recursion(s,v,n,c-1);

    return (max>k) ? max:k;
}


// Further thoughts:
// Same question as above. Also print out selected items in the knapsack.
//
// Algorithm: Backtracking
// We can reconstruct the list of items in the optimal solution by maintaining and following backpointers.
//
// When compute the max value for capacity i,
//   if item j is selected, backpointers[i] = j
//   if not, backpointers[i] = -1
//
// Then, we can backtrack the whole selection by tracing i in REVERSE order:
//   for(i=c; i>0;)
//   {
//     if backpointers[i] >= 0, i=i-s[backpointers[i]]
//     if backpointers[i] == -1, i=i-1
//   }
//
// Complexity
//  Time: O(n*C)
//  Space: O(C)

// *s: size array
// *v: value array
// n: total number of item types
// c: knapsack capacity
// backtrack: container of selected items
#include <stack>
int Knapsack_Backtrack(int *s, int *v, int n, int c, stack<int> &backtrack)
{
    if(!s||!v||n<=0||c<0) throw;
    if(!c) return 0;

    int *M=new int[c+1];
    int *backpointers=new int[c+1];

    M[0]=0;
    backpointers[0]=-1;

    for(int i=1;i<c+1;i++)
    {
        int max=0, pos=-1;
        M[i]=M[i-1];

        for(int j=0;j<n;j++)
        {
            int value=(i>=s[j]) ? M[i-s[j]]+v[j]:-1; // assume s[j]>0 and v[j]>0
            if(M[i]<value)
            {
                M[i]=value;
                pos=j;
            }
        }
        backpointers[i]=pos;
    }

    //cout<<endl<<"*** Debug Info ***"<<endl;
    //for(int i=0;i<c+1;i++) cout<<(M[i]<10?" ":"")<<M[i]<<" ";
    //cout<<endl;
    //for(int i=0;i<c+1;i++) cout<<(backpointers[i]<10&&backpointers[i]>=0?" ":"")<<backpointers[i]<<" ";
    //cout<<endl<<"*** Debug Info ***"<<endl<<endl;

    // trace backpointers - O(n)
    for(int i=c;i>0;)
    {
        while(i>0 && M[i]==M[i-1]) --i;
        if(backpointers[i]>=0)
        {
            backtrack.push(v[backpointers[i]]);
            i-=s[backpointers[i]];
        }
        else
            --i;
    }

    int maxValue=M[c];
    delete[] M;
    delete[] backpointers;
    return maxValue;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int capacity=22;
    int s[]={22, 8,5,11,4,6,15,10}; // size array
    int v[]={17,11,7,12,3,5,12, 9}; // value array

    if (sizeof(s)/sizeof(s[0]) != sizeof(v)/sizeof(v[0]))
    {
        cout<<"Invalid Inputs"<<endl;
        return getchar();
    }
    int n=sizeof(v)/sizeof(v[0]);

    for(int i=0;i<n;i++) cout<<(!i?"size: {":"")<<s[i]<<(i<n-1?", ":" }");
    cout<<endl;
    for(int i=0;i<n;i++) cout<<(!i?"value: {":"")<<v[i]<<(i<n-1?", ":" }");
    cout<<endl<<"Knapsack capacity: "<<capacity<<endl;

    stack<int> bt;
    int maxValue=Knapsack_Backtrack(s,v,n,capacity,bt);
    cout<<"Maximum value is "<<maxValue<<(!bt.empty()?": ":"");

    // output selected items
    while(!bt.empty())
    {
        cout<<bt.top()<<((bt.size()>1)?", ":"");
        bt.pop();
    }

    return getchar();
}